// 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

// 思路：构建大小为k的小顶堆，然后遍历剩余n - k个元素，和堆顶比较，如果大于则交换并堆化，直到遍历结束，得到topk
// 时间复杂度：O(nlogk)，n是数组的长度，k是要求返回的元素个数
// 空间复杂度：O(n)，arr的大小

class HeapQueue {
    arr = []
    map = null
    constructor(arr, map) {
        this.map = map
        this.arr =  Array.from(new Set(arr))
    }
    buildMinHeap(k) {
        for (let i = Math.floor((k - 2) / 2); i >= 0; i--) {
            this.heapfiy(i, k - 1)            
        }
    }
    getCounts(index) {
        return this.map.get(this.arr[index])
    }

    heapfiy(start, end) {
        let leftIndex = 2 * start + 1
        let rightIndex = leftIndex + 1
        while (leftIndex <= end) {
            let minIndex = start
            if (this.getCounts(leftIndex) < this.getCounts(minIndex)) {
                minIndex = leftIndex
            }
            if (rightIndex <= end && this.getCounts(rightIndex) < this.getCounts(minIndex)) {
                minIndex = rightIndex
            }
            if (start === minIndex) {
                break
            }
            [this.arr[minIndex], this.arr[start]] = [this.arr[start], this.arr[minIndex]];
            start = minIndex
            leftIndex = 2 * start + 1
            rightIndex = leftIndex + 1
        }
    }
    getResult(k) {
        this.buildMinHeap(k)
        for (let i = k; i < this.arr.length; i++) {
            if (this.getCounts(i) > this.getCounts(0)) {
                [this.arr[i], this.arr[0]] =  [this.arr[0], this.arr[i]];
                this.heapfiy(0, k - 1)
            }
        }
        return this.arr.slice(0, k)
    }
}

function topKFrequent(arr, k) {
    let map = new Map
    for (const item of arr) {
        if (!map.has(item)) {
            map.set(item, 1)
        } else {
            map.set(item, map.get(item) + 1)
        }
    }
    return new HeapQueue(arr, map).getResult(k)
}

nums = [4,4,4,4,4,1,1,1,2,2,3], k = 2
nums =
[4,1,-1,2,-1,2,3]
nums =
[5,-3,9,1,7,7,9,10,2,2,10,10,3,-1,3,7,-9,-1,3,3]
k =
3
console.log(topKFrequent(nums, k))